#include <iostream>
#include <vector>
#include <list>

template<typename K, typename V>
class HashMap {
private:
    static const int DEFAULT_CAPACITY = 16;
    std::vector<std::list<std::pair<K, V>>> table;
    int capacity;
    int size;

    int hash(const K& key) {
        return std::hash<K>{}(key) % capacity;
    }

public:
    HashMap() : capacity(DEFAULT_CAPACITY), size(0) {
        table.resize(capacity);
    }

    void put(const K& key, const V& value) {
        int index = hash(key);
        for (auto& kv : table[index]) {
            if (kv.first == key) {
                kv.second = value;
                return;
            }
        }
        table[index].emplace_back(key, value);
        size++;

        if (size > capacity * 0.75) {
            resize();
        }
    }

    V get(const K& key) {
        int index = hash(key);
        for (const auto& kv : table[index]) {
            if (kv.first == key) {
                return kv.second;
            }
        }
        throw std::out_of_range("Key not found");
    }

    void remove(const K& key) {
        int index = hash(key);
        for (auto it = table[index].begin(); it != table[index].end(); ++it) {
            if (it->first == key) {
                table[index].erase(it);
                size--;
                return;
            }
        }
        throw std::out_of_range("Key not found");
    }

    int getSize() {
        return size;
    }

    bool isEmpty() {
        return size == 0;
    }

private:
    void resize() {
        capacity *= 2;
        std::vector<std::list<std::pair<K, V>>> newTable(capacity);
        for (const auto& bucket : table) {
            for (const auto& kv : bucket) {
                int newIndex = hash(kv.first);
                newTable[newIndex].emplace_back(kv.first, kv.second);
            }
        }
        table = std::move(newTable);
    }
};